package datastructure.tree;

import java.util.Stack;

/**
 *
 * @author Lei Zhang
 */

public class IterativeInorderTravel {
  
  public static void method1(TreeNode node) {
    //incoming node is root
    Stack<TreeNode> nodes = new Stack<TreeNode>();
    while (!nodes.isEmpty() || null != node) {
      if (null != node) {
        nodes.push(node);
        node = node.left;
      } else {
        node = nodes.pop();
        System.out.println("Node value: " + node.value);
        node = node.right;
      }
    }
  }

  public static void method2(TreeNode p) {
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(p);

    while (!stack.isEmpty()) {
      TreeNode n = stack.peek();
      if (n.left == null && n.right == null) {
        System.out.println(stack.pop().value);
      } else if (n.left != null && !n.isVisited) {
        stack.push(n.left);
        n.setVisited();
      } else if (n.right != null && n.isVisited) {

        System.out.println("Node value: " + stack.pop().value);
        stack.push(n.right);
        n.setVisited();
      } else {
        System.out.println("Node value: " + stack.pop().value);
      }
    }
  }

  public static void main(String args[]) {

    TreeNode n1 = new TreeNode(1);
    TreeNode n2 = new TreeNode(2);
    TreeNode n3 = new TreeNode(3);
    TreeNode n4 = new TreeNode(4);
    TreeNode n5 = new TreeNode(5);
    TreeNode n6 = new TreeNode(6);

    n5.left = n2;
    n5.right = n6;

    n2.left = n1;
    n2.right = n4;

    n4.left = n3;

    IterativeInorderTravel.method1(n5);


  }
}
